package org.wiming;

import com.google.common.collect.Lists;

import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author : wenchao.long
 * @date : Created in 2021/01/21 9:52 周四
 * @description :
 */
public class ListNode {
    public int val;
    public ListNode next;

    private ListNode(int val) {
        this.val = val;
    }

    public static ListNode newInstance(int val) {
        return new ListNode(val);
    }

    public static ListNode createListNode(LinkedList<Integer> integers) {
        ListNode listNode = null;
        if (integers == null || integers.isEmpty()) {
            return null;
        }
        Integer val = integers.removeFirst();
        if (val != null) {
            listNode = newInstance(val);
            listNode.next = createListNode(integers);
        }
        return listNode;
    }

    /**
     * 顺序打印链表
     *
     * @return 链表节点 List
     */
    public List<Integer> print() {
        return print(this);
    }

    private List<Integer> print(ListNode root) {
        List<Integer> res = Lists.newArrayList();
        while (root != null) {
            res.add(root.val);
            root = root.next;
        }
        return res;
    }

    /**
     * 从尾到头打印链表
     *
     * @return 链表节点 List
     */
    public List<Integer> reverse() {
        return reverse(this);
    }

    private List<Integer> reverse(ListNode head) {
        List<Integer> reverses = Lists.newArrayList();
        recur(head, reverses);
        return reverses;
    }

    private void recur(ListNode head, List<Integer> reverses) {
        if (head == null) {
            return;
        }
        recur(head.next, reverses);
        reverses.add(head.val);
    }

    /**
     * 用链表实现从尾到头打印链表
     *
     * @return 链表节点 List
     */
    public List<Integer> reverseWithLinked() {
        return reverseWithLinked(this);
    }

    private List<Integer> reverseWithLinked(ListNode head) {
        Deque<Integer> queue = Lists.newLinkedList();
        while (head != null) {
            queue.addFirst(head.val);
            head = head.next;
        }
        return Lists.newArrayList(queue);
    }

    /**
     * 采用栈 反转链表
     *
     * @return 链表
     */
    public ListNode reverseWithStack() {
        return reverseWithStack(this);
    }

    private ListNode reverseWithStack(ListNode head) {
        if (head == null) {
            return null;
        }
        Stack<Integer> stack = new Stack<>();
        ListNode pre = head;
        while (pre != null) {
            stack.push(pre.val);
            pre = pre.next;
        }
        head.val = stack.pop();
        ListNode cur = head.next;
        while (!stack.isEmpty()) {
            cur.val = stack.pop();
            cur = cur.next;
        }
        return head;
    }

    /**
     * 反转链表
     *
     * @return 链表
     */
    public ListNode reverseListNode() {
        return reverseListNode(this);
    }

    private ListNode reverseListNode(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode temp;
        while (cur != null) {
            // 记录当前节点的下一个节点
            temp = cur.next;
            // 然后将当前节点指向pre
            cur.next = pre;
            // pre和cur节点都前进一位
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    /**
     * 获取链表的倒数第k个结点
     *
     * @param k k
     * @return 链表
     */
    public ListNode getKthFromEnd(int k) {
        return getKthFromEnd(this, k);
    }

    private ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null || k == 0) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        int tot = 0;
        while (fast != null) {
            if (tot >= k) {
                slow = slow.next;
            }
            fast = fast.next;
            ++tot;
        }
        if (tot < k) {
            return null;
        }
        return slow;
    }

    /**
     * 链表的中间节点
     * 采用双指针走法
     *
     * @return 中间链表
     */
    public ListNode middleNode() {
        return middleNode(this);
    }

    private ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 移除链表元素
     *
     * @param val 要移除的元素
     * @return 移除元素之后的链表
     */
    public ListNode removeElements(int val) {
        return removeElements(this, val);
    }

    private ListNode removeElements(ListNode head, int val) {
        // 设置一个辅助节点
        ListNode temp = ListNode.newInstance(0);
        temp.next = head;

        ListNode pre = temp;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }
        return temp.next;
    }
}
